
#ifndef __TLIST_H___
#define __TLIST_H___

#include <assert.h>
#include <stddef.h>
#include <nu_api.h>
#include "tapi_ppp.h"


struct __POSITION {};
typedef __POSITION* POSITION;

template <class TYPE, class ARG_TYPE = const TYPE&>
class TList
{
    class TNode {
public:
        TNode* pNext;
        TNode* pPrev;
        TYPE   data;
        void * __cdecl operator new(size_t size) {
            return nu_getTapiPPP()->ip_alloc(size);
        }
        void __cdecl operator delete(void *obj) {
            nu_getTapiPPP()->ip_free(obj);
        }
    };

public:
    TList() {
        m_pTailNode = m_pHeadNode = NULL;
        m_nCount = 0;
    }

    ~TList() {
        RemoveAll();
    }

    POSITION AddHead(ARG_TYPE newElement) {
        TNode *pNewNode = NewNode(NULL, m_pHeadNode, newElement);
        if (pNewNode == NULL) { return NULL; }

        if (m_pHeadNode != NULL) {
            m_pHeadNode->pPrev = pNewNode;
        }
        else {
            m_pTailNode = pNewNode;
        }
        m_pHeadNode = pNewNode;
        m_nCount++;
        return (POSITION) m_pHeadNode;
    }

    POSITION AddTail(ARG_TYPE newElement) {
        TNode *pNewNode = NewNode(m_pTailNode, NULL, newElement);
        if (pNewNode == NULL) { return NULL; }

        if (m_pTailNode != NULL) {
            m_pTailNode->pNext = pNewNode;
        }
        else {
            m_pHeadNode = pNewNode;
        }
        m_pTailNode = pNewNode;
        m_nCount++;
        return (POSITION) m_pTailNode;
    }

    POSITION InsertBefore(POSITION position, ARG_TYPE newElement)
    {
    	assert(this);
    	if (position == NULL) {
    		return AddHead(newElement);
        }

    	// Insert it before position
    	TNode* pOldNode = (TNode*) position;
    	TNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode, newElement);
    	if (pOldNode->pPrev != NULL) {
    		pOldNode->pPrev->pNext = pNewNode;
    	}
    	else {
    		m_pHeadNode = pNewNode;
    	}
    	pOldNode->pPrev = pNewNode;
        m_nCount++;
    	return (POSITION) pNewNode;
    }

    POSITION InsertAfter(POSITION position, ARG_TYPE newElement)
    {
    	assert(this);
    	if (position == NULL) {
    		return AddTail(newElement);
        }
    	// Insert it before position
    	TNode* pOldNode = (TNode*) position;
    	TNode* pNewNode = NewNode(pOldNode, pOldNode->pNext, newElement);
    	if (pOldNode->pNext != NULL) {
       		pOldNode->pNext->pPrev = pNewNode;
    	}
    	else {
    		m_pTailNode = pNewNode;
    	}
    	pOldNode->pNext = pNewNode;
        m_nCount++;
    	return (POSITION) pNewNode;
    }

    TYPE RemoveHead() {
        assert(m_pHeadNode != NULL);
        TNode* pOldNode = m_pHeadNode;
        TYPE returnValue = pOldNode->data;

        m_pHeadNode = pOldNode->pNext;
        if (m_pHeadNode != NULL) {
            m_pHeadNode->pPrev = NULL;
        }
        else {
            m_pTailNode = NULL;
        }
        FreeNode(pOldNode);
        m_nCount--;

        return returnValue;
    }

    TYPE RemoveTail() {
        assert(m_pTailNode != NULL);
        TNode* pOldNode = m_pTailNode;
        TYPE returnValue = pOldNode->data;

        m_pTailNode = pOldNode->pPrev;
        if (m_pTailNode != NULL) {
            m_pTailNode->pNext = NULL;
        }
        else {
            m_pHeadNode = NULL;
        }
        FreeNode(pOldNode);
        m_nCount--;
        return returnValue;
    }

    TYPE& GetHead() {
        assert(m_pHeadNode != NULL);
        return m_pHeadNode->data;
    }

    TYPE& GetTail() {
        assert(m_pTailNode != NULL);
        return m_pTailNode->data;
    }

    POSITION GetHeadPosition() const
    { return (POSITION) m_pHeadNode; }

    POSITION GetTailPosition() const
    { return (POSITION) m_pTailNode; }

    TYPE& GetNext(POSITION& rPosition) // return *Position++
    { TNode* pNode = (TNode*) rPosition;
        assert(pNode);
        rPosition = (POSITION) pNode->pNext;
        return pNode->data; }

    TYPE& GetPrev(POSITION& rPosition) // return *Position--
    { TNode* pNode = (TNode*) rPosition;
        assert(pNode);
        rPosition = (POSITION) pNode->pPrev;
        return pNode->data; }

    TYPE& GetAt(POSITION position)
    { TNode* pNode = (TNode*) position;
        assert(pNode);
        return pNode->data; }

    void SetAt(POSITION pos, ARG_TYPE newElement)
    { TNode* pNode = (TNode*) pos;
        assert(pNode);
        pNode->data = newElement; }

    void RemoveAt(POSITION position)
    {
        TNode* pOldNode = (TNode*) position;
        assert(pOldNode);

        // remove pOldNode from list
        if (pOldNode == m_pHeadNode) {
            m_pHeadNode = pOldNode->pNext;
        }
        else {
            assert(pOldNode->pPrev);
            pOldNode->pPrev->pNext = pOldNode->pNext;
        }
        if (pOldNode == m_pTailNode) {
            m_pTailNode = pOldNode->pPrev;
        }
        else
        {
            assert(pOldNode->pNext);
            pOldNode->pNext->pPrev = pOldNode->pPrev;
        }
        FreeNode(pOldNode);
        m_nCount--;
    }

    void RemoveAll() {
        while (GetCount() > 0) {
            RemoveHead();
        }
        m_pHeadNode = m_pTailNode = NULL;
        m_nCount = 0;
    }

    int GetCount() const { return m_nCount; }

    TList& operator =(TList &src) {
        RemoveAll();
        POSITION ps;
        ps = src.GetHeadPosition();
        while (ps != NULL) {
            AddTail(src.GetNext(ps));
        }
        return *this;
    }

private:
    TList(TList &src) {}

    TNode *NewNode(TNode *prev, TNode *next, ARG_TYPE newElement) {
        TNode *pNewNode = new TNode;
        if (pNewNode == NULL) { return NULL; }
        pNewNode->data = newElement;
        pNewNode->pPrev = prev;
        pNewNode->pNext = next;
        return pNewNode;
    }

    void FreeNode(TNode *pOldNode) {
        delete pOldNode;
    }

    TNode       *m_pTailNode, *m_pHeadNode;
    int         m_nCount;
};

#endif /* __TLIST_H___ */

